SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Grover's algorithm</title>

</head>

Grover's algorithm

</h1>

</header>

In <a href="Quantum_computing" title="Quantum computing">quantum computing</a>, Grover's algorithm, also known as the quantum search algorithm, is a <a href="Quantum_algorithm" title="Quantum algorithm">quantum algorithm</a> for unstructured search that finds <a href="With_high_probability" title="With high probability">with high probability</a> the unique input to a <a href="Black_box" title="Black box">black box</a> function that produces a particular output value, using just <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O({\sqrt {N}})}">

<msqrt>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O({\sqrt {N}})}</annotation>

</semantics>

</math><img src="./6a8566840a0a5d4480a0b8ed63d0717c3a89ec9a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.582ex; height:3.176ex;" alt="{\displaystyle O({\sqrt {N}})}" loading="lazy"> evaluations of the function, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math><img src="./f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy"> is the size of the function's <a href="Domain_of_a_function" title="Domain of a function">domain</a>. It was devised by <a href="Lov_Grover" title="Lov Grover">Lov Grover</a> in 1996.<a href="#cite_note-grover-1">[1]</a>

The analogous problem in classical computation would have a <a href="Query_complexity" title="Query complexity">query complexity</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(N)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(N)}</annotation>

</semantics>

</math><img src="./78484c5c26cfc97bb3b915418caa09454421e80b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.646ex; height:2.843ex;" alt="{\displaystyle O(N)}" loading="lazy"> (i.e., the function would have to be evaluated <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(N)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(N)}</annotation>

</semantics>

</math><img src="./78484c5c26cfc97bb3b915418caa09454421e80b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.646ex; height:2.843ex;" alt="{\displaystyle O(N)}" loading="lazy"> times: there is no better approach than trying out all input values one after the other, which, on average, takes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N/2}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N/2}</annotation>

</semantics>

</math><img src="./45c51c21b2bc7ea5e2fcae8f0f4aa49f6f19ebaf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.389ex; height:2.843ex;" alt="{\displaystyle N/2}" loading="lazy"> steps).<a href="#cite_note-grover-1">[1]</a>

<a href="Charles_H._Bennett_(physicist)" title="Charles H. Bennett (physicist)">Charles H. Bennett</a>, Ethan Bernstein, <a href="Gilles_Brassard" title="Gilles Brassard">Gilles Brassard</a>, and <a href="Umesh_Vazirani" title="Umesh Vazirani">Umesh Vazirani</a> proved that any quantum solution to the problem needs to evaluate the function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Omega ({\sqrt {N}})}">

<msqrt>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Omega ({\sqrt {N}})}</annotation>

</semantics>

</math><img src="./e867ed0a6f326f2d3b004c4638346bc5d4a9757f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.487ex; height:3.176ex;" alt="{\displaystyle \Omega ({\sqrt {N}})}" loading="lazy"> times, so Grover's algorithm is <a href="Asymptotically_optimal_algorithm" title="Asymptotically optimal algorithm">asymptotically optimal</a>.<a href="#cite_note-bennett_1997-2">[2]</a> Since classical algorithms for <a href="NP-completeness" title="NP-completeness">NP-complete problems</a> require exponentially many steps, and Grover's algorithm provides at most a quadratic speedup over the classical solution for unstructured search, this suggests that Grover's algorithm by itself will not provide <a href="Time_complexity" title="Time complexity">polynomial-time</a> solutions for NP-complete problems (as the square root of an exponential function is still an exponential, not a polynomial function).<a href="#cite_note-Nielsen-Chuang-3">[3]</a>

Unlike other quantum algorithms, which may provide exponential speedup over their classical counterparts, Grover's algorithm provides only a quadratic speedup. However, even quadratic speedup is considerable when <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math><img src="./f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy"> is large, and Grover's algorithm can be applied to speed up broad classes of algorithms.<a href="#cite_note-Nielsen-Chuang-3">[3]</a> Grover's algorithm could <a href="Brute-force_attack" title="Brute-force attack">brute-force</a> a 128-bit symmetric cryptographic key in roughly 264 iterations, or a 256-bit key in roughly 2128 iterations. It may not be the case that Grover's algorithm poses a significantly increased risk to encryption over existing classical algorithms, however.<a href="#cite_note-djb-groverr-4">[4]</a>

<div class="mw-heading mw-heading2"><h2 id="Applications_and_limitations">Applications and limitations</h2></div>

Grover's algorithm, along with variants like <a href="Amplitude_amplification" title="Amplitude amplification">amplitude amplification</a>, can be used to speed up a broad range of algorithms.<a href="#cite_note-5">[5]</a><a href="#cite_note-Ambaianis04-6">[6]</a><a href="#cite_note-7">[7]</a> In particular, algorithms for NP-complete problems which contain exhaustive search as a subroutine can be sped up by Grover's algorithm.<a href="#cite_note-Ambaianis04-6">[6]</a> The current theoretical best algorithm, in terms of worst-case complexity, for <a href="3SAT" class="mw-redirect" title="3SAT">3SAT</a> is one such example. Generic <a href="Constraint_satisfaction_problem" title="Constraint satisfaction problem">constraint satisfaction problems</a> also see quadratic speedups with Grover.<a href="#cite_note-8">[8]</a> These algorithms do not require that the input be given in the form of an oracle, since Grover's algorithm is being applied with an explicit function, e.g. the function checking that a set of bits satisfies a 3SAT instance. However, it is unclear whether Grover's algorithm could speed up best practical algorithms for these problems.

Grover's algorithm can also give provable speedups for black-box problems in <a href="Quantum_complexity_theory#Quantum_query_complexity" title="Quantum complexity theory">quantum query complexity</a>, including element distinctness<a href="#cite_note-9">[9]</a> and the <a href="Collision_problem" title="Collision problem">collision problem</a><a href="#cite_note-10">[10]</a> (solved with the <a href="BHT_algorithm" title="BHT algorithm">Brassard–Høyer–Tapp algorithm</a>). In these types of problems, one treats the oracle function f as a database, and the goal is to use the quantum query to this function as few times as possible.

<div class="mw-heading mw-heading3"><h3 id="Cryptography">Cryptography</h3></div>

Grover's algorithm essentially solves the task of function inversion. Roughly speaking, if we have a function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y=f(x)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y=f(x)}</annotation>

</semantics>

</math><img src="./2311a6a75c54b0ea085a381ba472c31d59321514.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.672ex; height:2.843ex;" alt="{\displaystyle y=f(x)}" loading="lazy"> that can be evaluated on a quantum computer, Grover's algorithm allows us to calculate <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math><img src="./87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"> when given <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math><img src="./b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy">. Consequently, Grover's algorithm gives broad asymptotic speed-ups to many kinds of <a href="Brute-force_attack" title="Brute-force attack">brute-force attacks</a> on <a href="Symmetric-key_algorithm" title="Symmetric-key algorithm">symmetric-key cryptography</a>, including <a href="Collision_attack" title="Collision attack">collision attacks</a> and <a href="Pre-image_attack" class="mw-redirect" title="Pre-image attack">pre-image attacks</a>.<a href="#cite_note-11">[11]</a> However, this may not necessarily be the most efficient algorithm since, for example, the <a href="Pollard's_rho_algorithm" title="Pollard's rho algorithm">Pollard's rho algorithm</a> is able to find a collision in <a href="SHA-2" title="SHA-2">SHA-2</a> more efficiently than Grover's algorithm.<a href="#cite_note-12">[12]</a>

<div class="mw-heading mw-heading3"><h3 id="Limitations">Limitations</h3></div>

Grover's original paper described the algorithm as a database search algorithm, and this description is still common. The database in this analogy is a table of all of the function's outputs, indexed by the corresponding input. However, this database is not represented explicitly. Instead, an oracle is invoked to evaluate an item by its index. Reading a full database item by item and converting it into such a representation may take a lot longer than Grover's search. To account for such effects, Grover's algorithm can be viewed as solving an equation or <a href="Constraint_satisfaction_problem" title="Constraint satisfaction problem">satisfying a constraint</a>. In such applications, the oracle is a way to check the constraint and is not related to the search algorithm. This separation usually prevents algorithmic optimizations, whereas conventional search algorithms often rely on such optimizations and avoid exhaustive search.<a href="#cite_note-Viamontes-13">[13]</a> Fortunately, fast Grover's oracle implementation is possible for many constraint satisfaction and optimization problems.<a href="#cite_note-sinitsyn23-14">[14]</a>

The major barrier to instantiating a speedup from Grover's algorithm is that the quadratic speedup achieved is too modest to overcome the large overhead of near-term quantum computers.<a href="#cite_note-15">[15]</a> However, later generations of <a href="Quantum_threshold_theorem" class="mw-redirect" title="Quantum threshold theorem">fault-tolerant</a> quantum computers with better hardware performance may be able to realize these speedups for practical instances of data.

<div class="mw-heading mw-heading2"><h2 id="Problem_description">Problem description</h2></div>

As input for Grover's algorithm, suppose we have a function <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f\colon \{0,1,\ldots ,N-1\}\to \{0,1\}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f\colon \{0,1,\ldots ,N-1\}\to \{0,1\}}</annotation>

</semantics>

</math><img src="./1cf1bdc1be997a808ce588691d32fd183ffc696c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:28.539ex; height:2.843ex;" alt="{\displaystyle f\colon \{0,1,\ldots ,N-1\}\to \{0,1\}}" loading="lazy">. In the "unstructured database" analogy, the domain represent indices to a database, and f(x) = 1 if and only if the data that x points to satisfies the search criterion. We additionally assume that only one index satisfies f(x) = 1, and we call this index ω. Our goal is to identify ω.

We can access f with a <a href="Subroutine" class="mw-redirect" title="Subroutine">subroutine</a> (sometimes called an <a href="Oracle_machine" title="Oracle machine">oracle</a>) in the form of a <a href="Unitary_operator" title="Unitary operator">unitary operator</a> Uω that acts as follows:

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mtd>

<mtd>

</mrow>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mtd>

<mtd>

</mrow>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{cases}U_{\omega }|x\rangle =-|x\rangle &{\text{for }}x=\omega {\text{, that is, }}f(x)=1,\\U_{\omega }|x\rangle =|x\rangle &{\text{for }}x\neq \omega {\text{, that is, }}f(x)=0.\end{cases}}}</annotation>

</semantics>

</math>

This uses the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math><img src="./f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy">-dimensional <a href="Mathematical_formulation_of_quantum_mechanics" title="Mathematical formulation of quantum mechanics">state space</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {H}}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {H}}}</annotation>

</semantics>

</math><img src="./19ef4c7b923a5125ac91aa491838a95ee15b804f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.964ex; height:2.176ex;" alt="{\displaystyle {\mathcal {H}}}" loading="lazy">, which is supplied by a <a href="Quantum_register" title="Quantum register">register</a> with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=\lceil \log _{2}N\rceil }">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=\lceil \log _{2}N\rceil }</annotation>

</semantics>

</math><img src="./51a072e4dd331b8cd6513935f5de2f3a9f87bc14.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.035ex; height:2.843ex;" alt="{\displaystyle n=\lceil \log _{2}N\rceil }" loading="lazy"> <a href="Qubit" title="Qubit">qubits</a>.

This is often written as

<msub>

</mrow>

</msub>

</mrow>

<msup>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U_{\omega }|x\rangle =(-1)^{f(x)}|x\rangle .}</annotation>

</semantics>

</math>

Grover's algorithm outputs ω with probability at least 1/2 using <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O({\sqrt {N}})}">

<msqrt>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O({\sqrt {N}})}</annotation>

</semantics>

</math><img src="./6a8566840a0a5d4480a0b8ed63d0717c3a89ec9a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.582ex; height:3.176ex;" alt="{\displaystyle O({\sqrt {N}})}" loading="lazy"> applications of Uω. This probability can be made arbitrarily large by running Grover's algorithm multiple times. If one runs Grover's algorithm until ω is found, the <a href="Expected_value" title="Expected value">expected</a> number of applications is still <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O({\sqrt {N}})}">

<msqrt>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O({\sqrt {N}})}</annotation>

</semantics>

</math><img src="./6a8566840a0a5d4480a0b8ed63d0717c3a89ec9a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.582ex; height:3.176ex;" alt="{\displaystyle O({\sqrt {N}})}" loading="lazy">, since it will only be run twice on average.

<div class="mw-heading mw-heading3"><h3 id="Alternative_oracle_definition">Alternative oracle definition</h3></div>

This section compares the above oracle <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U_{\omega }}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U_{\omega }}</annotation>

</semantics>

</math><img src="./f6ac6ea54ea1b4c9d302cdb049c96d4634e76413.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.842ex; height:2.509ex;" alt="{\displaystyle U_{\omega }}" loading="lazy"> with an oracle <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U_{f}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U_{f}}</annotation>

</semantics>

</math><img src="./f7be3c3c86d5d87a48bec069e8477dd5a4823fcc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.724ex; height:2.843ex;" alt="{\displaystyle U_{f}}" loading="lazy">.

Uω is different from the standard <a href="Oracle_machine" title="Oracle machine">quantum oracle</a> for a function f. This standard oracle, denoted here as Uf, uses an <a href="Ancilla_bit" title="Ancilla bit">ancillary qubit</a> system. The operation then represents an inversion (<a href="Quantum_gate" class="mw-redirect" title="Quantum gate">NOT gate</a>) on the main system conditioned by the value of f(x) from the ancillary system:

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mrow>

</mrow>

</mtd>

<mtd>

</mrow>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mrow>

</mrow>

</mtd>

<mtd>

</mrow>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{cases}U_{f}|x\rangle |y\rangle =|x\rangle |\neg y\rangle &{\text{for }}x=\omega {\text{, that is, }}f(x)=1,\\U_{f}|x\rangle |y\rangle =|x\rangle |y\rangle &{\text{for }}x\neq \omega {\text{, that is, }}f(x)=0,\end{cases}}}</annotation>

</semantics>

</math>

or briefly,

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U_{f}|x\rangle |y\rangle =|x\rangle |y\oplus f(x)\rangle .}</annotation>

</semantics>

</math>

These oracles are typically realized using <a href="Uncomputation" title="Uncomputation">uncomputation</a>.

If we are given Uf as our oracle, then we can also implement Uω, since Uω is Uf when the ancillary qubit is in the state <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |-\rangle ={\frac {1}{\sqrt {2}}}{\big (}|0\rangle -|1\rangle {\big )}=H|1\rangle }">

</mrow>

<mfrac>

<msqrt>

</msqrt>

</mfrac>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |-\rangle ={\frac {1}{\sqrt {2}}}{\big (}|0\rangle -|1\rangle {\big )}=H|1\rangle }</annotation>

</semantics>

</math><img src="./74f975173a35cd101ecd9f131615f012bcd216e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.838ex; width:28.667ex; height:6.176ex;" alt="{\displaystyle |-\rangle ={\frac {1}{\sqrt {2}}}{\big (}|0\rangle -|1\rangle {\big )}=H|1\rangle }" loading="lazy">:

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mrow>

</mrow>

</mtd>

<mtd>

<mfrac>

<msqrt>

</msqrt>

</mfrac>

</mrow>

<mrow>

<mrow>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mrow>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<mfrac>

<msqrt>

</msqrt>

</mfrac>

</mrow>

<mrow>

<mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<mrow>

<mtr>

<mtd>

<mfrac>

<msqrt>

</msqrt>

</mfrac>

</mrow>

<mrow>

<mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mtd>

<mtd>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<mfrac>

<msqrt>

</msqrt>

</mfrac>

</mrow>

<mrow>

<mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mrow>

</mtd>

<mtd>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}U_{f}{\big (}|x\rangle \otimes |-\rangle {\big )}&={\frac {1}{\sqrt {2}}}\left(U_{f}|x\rangle |0\rangle -U_{f}|x\rangle |1\rangle \right)\\&={\frac {1}{\sqrt {2}}}\left(|x\rangle |0\oplus f(x)\rangle -|x\rangle |1\oplus f(x)\rangle \right)\\&={\begin{cases}{\frac {1}{\sqrt {2}}}\left(-|x\rangle |0\rangle +|x\rangle |1\rangle \right)&{\text{if }}f(x)=1,\\{\frac {1}{\sqrt {2}}}\left(|x\rangle |0\rangle -|x\rangle |1\rangle \right)&{\text{if }}f(x)=0\end{cases}}\\&=(U_{\omega }|x\rangle )\otimes |-\rangle \end{aligned}}}</annotation>

</semantics>

</math>

So, Grover's algorithm can be run regardless of which oracle is given.<a href="#cite_note-Nielsen-Chuang-3">[3]</a> If Uf is given, then we must maintain an additional qubit in the state <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |-\rangle }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |-\rangle }</annotation>

</semantics>

</math><img src="./7da62e696eae51c2d89944b647e24b41cafb2f1e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.36ex; height:2.843ex;" alt="{\displaystyle |-\rangle }" loading="lazy"> and apply Uf in place of Uω.

<div class="mw-heading mw-heading2"><h2 id="Algorithm">Algorithm</h2></div>

The steps of Grover's algorithm are given as follows:

<ol><li>Initialize the system to the uniform superposition over all states <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |s\rangle ={\frac {1}{\sqrt {N}}}\sum _{x=0}^{N-1}|x\rangle .}">

</mrow>

<mfrac>

<msqrt>

</msqrt>

</mfrac>

</mrow>

</mrow>

</mrow>

</munderover>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |s\rangle ={\frac {1}{\sqrt {N}}}\sum _{x=0}^{N-1}|x\rangle .}</annotation>

</semantics>

</math><img src="./dfb6b8ee0d74bce6f17cb47ab8ae127da3b699dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:18.438ex; height:7.343ex;" alt="{\displaystyle |s\rangle ={\frac {1}{\sqrt {N}}}\sum _{x=0}^{N-1}|x\rangle .}" loading="lazy"></li>

<li>Perform the following "Grover iteration" <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r(N)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r(N)}</annotation>

</semantics>

</math><img src="./c9ac6097c5943a4ae5d12f95478b55a2acc93b7d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.922ex; height:2.843ex;" alt="{\displaystyle r(N)}" loading="lazy"> times:

<ol><li>Apply the operator <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U_{\omega }}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U_{\omega }}</annotation>

</semantics>

</math><img src="./f6ac6ea54ea1b4c9d302cdb049c96d4634e76413.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.842ex; height:2.509ex;" alt="{\displaystyle U_{\omega }}" loading="lazy"></li>

<li>Apply the Grover diffusion operator <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U_{s}=2\left|s\right\rangle \!\!\left\langle s\right|-I}">

<msub>

</mrow>

</msub>

<mrow>

</mrow>

<mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U_{s}=2\left|s\right\rangle \!\!\left\langle s\right|-I}</annotation>

</semantics>

</math><img src="./972527d16486e1b79d95a84bd30d4e9631c0bb02.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.148ex; height:2.843ex;" alt="{\displaystyle U_{s}=2\left|s\right\rangle \!\!\left\langle s\right|-I}" loading="lazy"></li></ol></li>

<li><a href="Measurement_in_quantum_mechanics" title="Measurement in quantum mechanics">Measure</a> the resulting quantum state in the computational basis.</li></ol>

For the correctly chosen value of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r}</annotation>

</semantics>

</math><img src="./0d1ecb613aa2984f0576f70f86650b7c2a132538.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:1.676ex;" alt="{\displaystyle r}" loading="lazy">, the output will be <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |\omega \rangle }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |\omega \rangle }</annotation>

</semantics>

</math><img src="./731536978690a6020df5ab318b08eaf19ebc2f25.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.997ex; height:2.843ex;" alt="{\displaystyle |\omega \rangle }" loading="lazy"> with probability approaching 1 for N ≫ 1. Analysis shows that this eventual value for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r(N)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r(N)}</annotation>

</semantics>

</math><img src="./c9ac6097c5943a4ae5d12f95478b55a2acc93b7d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.922ex; height:2.843ex;" alt="{\displaystyle r(N)}" loading="lazy"> satisfies <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r(N)\leq {\Big \lceil }{\frac {\pi }{4}}{\sqrt {N}}{\Big \rceil }}">

</mrow>

<mfrac>

</mfrac>

</mrow>

<msqrt>

</msqrt>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r(N)\leq {\Big \lceil }{\frac {\pi }{4}}{\sqrt {N}}{\Big \rceil }}</annotation>

</semantics>

</math><img src="./a1b68b5c6cd30fa17877a24bcd0bb265579c156f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:16.643ex; height:4.843ex;" alt="{\displaystyle r(N)\leq {\Big \lceil }{\frac {\pi }{4}}{\sqrt {N}}{\Big \rceil }}" loading="lazy">.

Implementing the steps for this algorithm can be done using a number of gates linear in the number of qubits.<a href="#cite_note-Nielsen-Chuang-3">[3]</a> Thus, the gate complexity of this algorithm is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log(N)r(N))}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log(N)r(N))}</annotation>

</semantics>

</math><img src="./d10826463b7bda7bf8103c689600c4fffe26fe55.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.349ex; height:2.843ex;" alt="{\displaystyle O(\log(N)r(N))}" loading="lazy">, or <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log(N))}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(\log(N))}</annotation>

</semantics>

</math><img src="./a1da4967a408abab26fdad1cc589221e7c1bf30b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.427ex; height:2.843ex;" alt="{\displaystyle O(\log(N))}" loading="lazy"> per iteration.

<div class="mw-heading mw-heading2"><h2 id="Geometric_proof">Geometric proof</h2></div>

There is a geometric interpretation of Grover's algorithm, following from the observation that the quantum state of Grover's algorithm stays in a two-dimensional subspace after each step. Consider the plane spanned by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |s\rangle }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |s\rangle }</annotation>

</semantics>

</math><img src="./a43a9ddce45b6fdef3363ba15c4cd2e090007f5d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.642ex; height:2.843ex;" alt="{\displaystyle |s\rangle }" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |\omega \rangle }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |\omega \rangle }</annotation>

</semantics>

</math><img src="./731536978690a6020df5ab318b08eaf19ebc2f25.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.997ex; height:2.843ex;" alt="{\displaystyle |\omega \rangle }" loading="lazy">; equivalently, the plane spanned by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |\omega \rangle }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |\omega \rangle }</annotation>

</semantics>

</math><img src="./731536978690a6020df5ab318b08eaf19ebc2f25.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.997ex; height:2.843ex;" alt="{\displaystyle |\omega \rangle }" loading="lazy"> and the perpendicular <a href="Bra%E2%80%93ket_notation" title="Bra–ket notation">ket</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \textstyle |s'\rangle ={\frac {1}{\sqrt {N-1}}}\sum _{x\neq \omega }|x\rangle }">

</mrow>

<msup>

</msup>

<mfrac>

<msqrt>

</msqrt>

</mfrac>

</mrow>

</mrow>

</munder>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \textstyle |s'\rangle ={\frac {1}{\sqrt {N-1}}}\sum _{x\neq \omega }|x\rangle }</annotation>

</semantics>

</math><img src="./6e4c127051a3d31f15b93375f2b2e7e6808bb003.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:21.772ex; height:4.176ex;" alt="{\displaystyle \textstyle |s'\rangle ={\frac {1}{\sqrt {N-1}}}\sum _{x\neq \omega }|x\rangle }" loading="lazy">.

Grover's algorithm begins with the initial ket <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |s\rangle }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |s\rangle }</annotation>

</semantics>

</math><img src="./a43a9ddce45b6fdef3363ba15c4cd2e090007f5d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.642ex; height:2.843ex;" alt="{\displaystyle |s\rangle }" loading="lazy">, which lies in the subspace. The operator <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U_{\omega }}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U_{\omega }}</annotation>

</semantics>

</math><img src="./f6ac6ea54ea1b4c9d302cdb049c96d4634e76413.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.842ex; height:2.509ex;" alt="{\displaystyle U_{\omega }}" loading="lazy"> is a reflection at the hyperplane orthogonal to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |\omega \rangle }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |\omega \rangle }</annotation>

</semantics>

</math><img src="./731536978690a6020df5ab318b08eaf19ebc2f25.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.997ex; height:2.843ex;" alt="{\displaystyle |\omega \rangle }" loading="lazy"> for vectors in the plane spanned by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |s'\rangle }">

</mrow>

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |s'\rangle }</annotation>

</semantics>

</math><img src="./707cfe703f4cca5d54714cb1c7ed5406c66c4734.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.327ex; height:3.009ex;" alt="{\displaystyle |s'\rangle }" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |\omega \rangle }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |\omega \rangle }</annotation>

</semantics>

</math><img src="./731536978690a6020df5ab318b08eaf19ebc2f25.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.997ex; height:2.843ex;" alt="{\displaystyle |\omega \rangle }" loading="lazy">, i.e. it acts as a reflection across <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |s'\rangle }">

</mrow>

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |s'\rangle }</annotation>

</semantics>

</math><img src="./707cfe703f4cca5d54714cb1c7ed5406c66c4734.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.327ex; height:3.009ex;" alt="{\displaystyle |s'\rangle }" loading="lazy">. This can be seen by writing <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U_{\omega }}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U_{\omega }}</annotation>

</semantics>

</math><img src="./f6ac6ea54ea1b4c9d302cdb049c96d4634e76413.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.842ex; height:2.509ex;" alt="{\displaystyle U_{\omega }}" loading="lazy"> in the form of a <a href="Householder_transformation" title="Householder transformation">Householder reflection</a>:

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U_{\omega }=I-2|\omega \rangle \langle \omega |.}</annotation>

</semantics>

</math>

The operator <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U_{s}=2|s\rangle \langle s|-I}">

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U_{s}=2|s\rangle \langle s|-I}</annotation>

</semantics>

</math><img src="./076d602d4991d86c9038313403aa33d4e1a655e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:16.148ex; height:2.843ex;" alt="{\displaystyle U_{s}=2|s\rangle \langle s|-I}" loading="lazy"> is a reflection through <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |s\rangle }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |s\rangle }</annotation>

</semantics>

</math><img src="./a43a9ddce45b6fdef3363ba15c4cd2e090007f5d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.642ex; height:2.843ex;" alt="{\displaystyle |s\rangle }" loading="lazy">. Both operators <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U_{s}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U_{s}}</annotation>

</semantics>

</math><img src="./e61d1a3cbea2c02997c2a9416a0bd82fed911f75.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.591ex; height:2.509ex;" alt="{\displaystyle U_{s}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U_{\omega }}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U_{\omega }}</annotation>

</semantics>

</math><img src="./f6ac6ea54ea1b4c9d302cdb049c96d4634e76413.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.842ex; height:2.509ex;" alt="{\displaystyle U_{\omega }}" loading="lazy"> take states in the plane spanned by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |s'\rangle }">

</mrow>

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |s'\rangle }</annotation>

</semantics>

</math><img src="./707cfe703f4cca5d54714cb1c7ed5406c66c4734.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.327ex; height:3.009ex;" alt="{\displaystyle |s'\rangle }" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |\omega \rangle }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |\omega \rangle }</annotation>

</semantics>

</math><img src="./731536978690a6020df5ab318b08eaf19ebc2f25.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.997ex; height:2.843ex;" alt="{\displaystyle |\omega \rangle }" loading="lazy"> to states in the plane. Therefore, Grover's algorithm stays in this plane for the entire algorithm.

It is straightforward to check that the operator <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U_{s}U_{\omega }}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U_{s}U_{\omega }}</annotation>

</semantics>

</math><img src="./ceec353e6604866b425dad0e1fe66fba9dc841ca.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.433ex; height:2.509ex;" alt="{\displaystyle U_{s}U_{\omega }}" loading="lazy"> of each Grover iteration step rotates the state vector by an angle of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \theta =2\arcsin {\tfrac {1}{\sqrt {N}}}}">

<mi>arcsin</mi>

<mfrac>

<msqrt>

</msqrt>

</mfrac>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \theta =2\arcsin {\tfrac {1}{\sqrt {N}}}}</annotation>

</semantics>

</math><img src="./f21e1d2b4dddde76ad05820b48749c1917ae12b7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:15.752ex; height:4.176ex;" alt="{\displaystyle \theta =2\arcsin {\tfrac {1}{\sqrt {N}}}}" loading="lazy">. So, with enough iterations, one can rotate from the initial state <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |s\rangle }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |s\rangle }</annotation>

</semantics>

</math><img src="./a43a9ddce45b6fdef3363ba15c4cd2e090007f5d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.642ex; height:2.843ex;" alt="{\displaystyle |s\rangle }" loading="lazy"> to the desired output state <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |\omega \rangle }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |\omega \rangle }</annotation>

</semantics>

</math><img src="./731536978690a6020df5ab318b08eaf19ebc2f25.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.997ex; height:2.843ex;" alt="{\displaystyle |\omega \rangle }" loading="lazy">. The initial ket is close to the state orthogonal to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |\omega \rangle }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |\omega \rangle }</annotation>

</semantics>

</math><img src="./731536978690a6020df5ab318b08eaf19ebc2f25.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.997ex; height:2.843ex;" alt="{\displaystyle |\omega \rangle }" loading="lazy">:

<msup>

</msup>

</mrow>

<msqrt>

<mfrac>

<mrow>

</mrow>

</mfrac>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \langle s'|s\rangle ={\sqrt {\frac {N-1}{N}}}.}</annotation>

</semantics>

</math>

In geometric terms, the angle <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \theta /2}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \theta /2}</annotation>

</semantics>

</math><img src="./74af4b205463ab5f0642165e85d0b372ff42d442.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.415ex; height:2.843ex;" alt="{\displaystyle \theta /2}" loading="lazy"> between <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |s\rangle }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |s\rangle }</annotation>

</semantics>

</math><img src="./a43a9ddce45b6fdef3363ba15c4cd2e090007f5d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.642ex; height:2.843ex;" alt="{\displaystyle |s\rangle }" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |s'\rangle }">

</mrow>

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |s'\rangle }</annotation>

</semantics>

</math><img src="./707cfe703f4cca5d54714cb1c7ed5406c66c4734.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:3.327ex; height:3.009ex;" alt="{\displaystyle |s'\rangle }" loading="lazy"> is given by

<mfrac>

</mfrac>

</mrow>

<mfrac>

<msqrt>

</msqrt>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sin {\frac {\theta }{2}}={\frac {1}{\sqrt {N}}}.}</annotation>

</semantics>

</math>

We need to stop when the state vector passes close to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |\omega \rangle }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |\omega \rangle }</annotation>

</semantics>

</math><img src="./731536978690a6020df5ab318b08eaf19ebc2f25.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.997ex; height:2.843ex;" alt="{\displaystyle |\omega \rangle }" loading="lazy">; after this, subsequent iterations rotate the state vector away from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle |\omega \rangle }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle |\omega \rangle }</annotation>

</semantics>

</math><img src="./731536978690a6020df5ab318b08eaf19ebc2f25.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:2.997ex; height:2.843ex;" alt="{\displaystyle |\omega \rangle }" loading="lazy">, reducing the probability of obtaining the correct answer. The exact probability of measuring the correct answer is

<msup>

</mrow>

</msup>

<mrow>

<mrow>

</mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \sin ^{2}\left({\Big (}r+{\frac {1}{2}}{\Big )}\theta \right),}</annotation>

</semantics>

</math>

where r is the (integer) number of Grover iterations. The earliest time that we get a near-optimal measurement is therefore <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r\approx \pi {\sqrt {N}}/4}">

<msqrt>

</msqrt>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r\approx \pi {\sqrt {N}}/4}</annotation>

</semantics>

</math><img src="./313d5618e49ca5f1b40236582973fe1519e37587.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.804ex; height:3.176ex;" alt="{\displaystyle r\approx \pi {\sqrt {N}}/4}" loading="lazy">.

<div class="mw-heading mw-heading2"><h2 id="Algebraic_proof">Algebraic proof</h2></div>

To complete the algebraic analysis, we need to find out what happens when we repeatedly apply <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U_{s}U_{\omega }}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U_{s}U_{\omega }}</annotation>

</semantics>

</math><img src="./ceec353e6604866b425dad0e1fe66fba9dc841ca.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.433ex; height:2.509ex;" alt="{\displaystyle U_{s}U_{\omega }}" loading="lazy">. A natural way to do this is by eigenvalue analysis of a matrix. Notice that during the entire computation, the state of the algorithm is a linear combination of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s}</annotation>

</semantics>

</math><img src="./01d131dfd7673938b947072a13a9744fe997e632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:1.676ex;" alt="{\displaystyle s}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \omega }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \omega }</annotation>

</semantics>

</math><img src="./48eff443f9de7a985bb94ca3bde20813ea737be8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.446ex; height:1.676ex;" alt="{\displaystyle \omega }" loading="lazy">. We can write the action of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U_{s}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U_{s}}</annotation>

</semantics>

</math><img src="./e61d1a3cbea2c02997c2a9416a0bd82fed911f75.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.591ex; height:2.509ex;" alt="{\displaystyle U_{s}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U_{\omega }}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U_{\omega }}</annotation>

</semantics>

</math><img src="./f6ac6ea54ea1b4c9d302cdb049c96d4634e76413.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.842ex; height:2.509ex;" alt="{\displaystyle U_{\omega }}" loading="lazy"> in the space spanned by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{|s\rangle ,|\omega \rangle \}}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{|s\rangle ,|\omega \rangle \}}</annotation>

</semantics>

</math><img src="./3ec05bda1ec6f4d83c4dd3c5f7bb0e09aa83f660.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.998ex; height:2.843ex;" alt="{\displaystyle \{|s\rangle ,|\omega \rangle \}}" loading="lazy"> as:

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mtd>

<mtd>

</mrow>

</mrow>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

<msqrt>

</msqrt>

</mrow>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

<mrow>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</mtd>

<mtd>

</mrow>

</mrow>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mrow>

<msqrt>

</msqrt>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

<mrow>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}U_{s}:a|\omega \rangle +b|s\rangle &\mapsto [|\omega \rangle \,|s\rangle ]{\begin{bmatrix}-1&0\\2/{\sqrt {N}}&1\end{bmatrix}}{\begin{bmatrix}a\\b\end{bmatrix}}.\\U_{\omega }:a|\omega \rangle +b|s\rangle &\mapsto [|\omega \rangle \,|s\rangle ]{\begin{bmatrix}-1&-2/{\sqrt {N}}\\0&1\end{bmatrix}}{\begin{bmatrix}a\\b\end{bmatrix}}.\end{aligned}}}</annotation>

</semantics>

</math><img src="./f048178f3328b2f80b4f7a5f94bc528c384f20ec.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -6.005ex; width:48.887ex; height:13.176ex;" alt="{\displaystyle {\begin{aligned}U_{s}:a|\omega \rangle +b|s\rangle &\mapsto [|\omega \rangle \,|s\rangle ]{\begin{bmatrix}-1&0\\2/{\sqrt {N}}&1\end{bmatrix}}{\begin{bmatrix}a\\b\end{bmatrix}}.\\U_{\omega }:a|\omega \rangle +b|s\rangle &\mapsto [|\omega \rangle \,|s\rangle ]{\begin{bmatrix}-1&-2/{\sqrt {N}}\\0&1\end{bmatrix}}{\begin{bmatrix}a\\b\end{bmatrix}}.\end{aligned}}}" loading="lazy">

So in the basis <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{|\omega \rangle ,|s\rangle \}}">

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{|\omega \rangle ,|s\rangle \}}</annotation>

</semantics>

</math><img src="./6fb8558534f57492f89bbb942fdbf1f3c977ad0f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.998ex; height:2.843ex;" alt="{\displaystyle \{|\omega \rangle ,|s\rangle \}}" loading="lazy"> (which is neither orthogonal nor a basis of the whole space) the action <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U_{s}U_{\omega }}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U_{s}U_{\omega }}</annotation>

</semantics>

</math><img src="./ceec353e6604866b425dad0e1fe66fba9dc841ca.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.433ex; height:2.509ex;" alt="{\displaystyle U_{s}U_{\omega }}" loading="lazy"> of applying <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U_{\omega }}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U_{\omega }}</annotation>

</semantics>

</math><img src="./f6ac6ea54ea1b4c9d302cdb049c96d4634e76413.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.842ex; height:2.509ex;" alt="{\displaystyle U_{\omega }}" loading="lazy"> followed by <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle U_{s}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U_{s}}</annotation>

</semantics>

</math><img src="./e61d1a3cbea2c02997c2a9416a0bd82fed911f75.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.591ex; height:2.509ex;" alt="{\displaystyle U_{s}}" loading="lazy"> is given by the matrix

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

<msqrt>

</msqrt>

</mrow>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mrow>

<msqrt>

</msqrt>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mrow>

<msqrt>

</msqrt>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

<msqrt>

</msqrt>

</mrow>

</mtd>

<mtd>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U_{s}U_{\omega }={\begin{bmatrix}-1&0\\2/{\sqrt {N}}&1\end{bmatrix}}{\begin{bmatrix}-1&-2/{\sqrt {N}}\\0&1\end{bmatrix}}={\begin{bmatrix}1&2/{\sqrt {N}}\\-2/{\sqrt {N}}&1-4/N\end{bmatrix}}.}</annotation>

</semantics>

</math>

This matrix happens to have a very convenient <a href="Jordan_form" class="mw-redirect" title="Jordan form">Jordan form</a>. If we define <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t=\arcsin(1/{\sqrt {N}})}">

<mi>arcsin</mi>

</mrow>

<msqrt>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t=\arcsin(1/{\sqrt {N}})}</annotation>

</semantics>

</math><img src="./73e841ee244fe0733b431c0c91ad6d4d9fadd60b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.034ex; height:3.176ex;" alt="{\displaystyle t=\arcsin(1/{\sqrt {N}})}" loading="lazy">, it is

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<mrow>

<mtr>

<mtd>

<msup>

</mrow>

</msup>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

</mtable>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle U_{s}U_{\omega }=M{\begin{bmatrix}e^{2it}&0\\0&e^{-2it}\end{bmatrix}}M^{-1}}</annotation>

</semantics>

</math>

where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M={\begin{bmatrix}-i&i\\e^{it}&e^{-it}\end{bmatrix}}.}">

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<msup>

</mrow>

</msup>

</mtd>

<mtd>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M={\begin{bmatrix}-i&i\\e^{it}&e^{-it}\end{bmatrix}}.}</annotation>

</semantics>

</math><img src="./43b28c4b371fb298f29bf8d682c9138efbdf19d3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:18.083ex; height:6.176ex;" alt="{\displaystyle M={\begin{bmatrix}-i&i\\e^{it}&e^{-it}\end{bmatrix}}.}" loading="lazy">

It follows that r-th power of the matrix (corresponding to r iterations) is

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<mrow>

<mtr>

<mtd>

<msup>

</mrow>

</msup>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

</mtable>

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (U_{s}U_{\omega })^{r}=M{\begin{bmatrix}e^{2rit}&0\\0&e^{-2rit}\end{bmatrix}}M^{-1}.}</annotation>

</semantics>

</math>

Using this form, we can use trigonometric identities to compute the probability of observing ω after r iterations mentioned in the previous section,

<msup>

<mrow>

<mrow>

<mrow>

<mtr>

<mtd>

</mrow>

</mtd>

<mtd>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<mrow>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mrow>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<mrow>

<mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \left|{\begin{bmatrix}\langle \omega |\omega \rangle &\langle \omega |s\rangle \end{bmatrix}}(U_{s}U_{\omega })^{r}{\begin{bmatrix}0\\1\end{bmatrix}}\right|^{2}=\sin ^{2}\left((2r+1)t\right).}</annotation>

</semantics>

</math>

Alternatively, one might reasonably imagine that a near-optimal time to distinguish would be when the angles 2rt and −2rt are as far apart as possible, which corresponds to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2rt\approx \pi /2}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2rt\approx \pi /2}</annotation>

</semantics>

</math><img src="./d041a42a614d75df1edad575021ec916b9383832.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.806ex; height:2.843ex;" alt="{\displaystyle 2rt\approx \pi /2}" loading="lazy">, or <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r=\pi /4t=\pi /4\arcsin(1/{\sqrt {N}})\approx \pi {\sqrt {N}}/4}">

</mrow>

</mrow>

<mi>arcsin</mi>

</mrow>

<msqrt>

</msqrt>

</mrow>

<msqrt>

</msqrt>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r=\pi /4t=\pi /4\arcsin(1/{\sqrt {N}})\approx \pi {\sqrt {N}}/4}</annotation>

</semantics>

</math><img src="./d799805ade1873fd700a32d33088e8b77a271bb6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:40.637ex; height:3.176ex;" alt="{\displaystyle r=\pi /4t=\pi /4\arcsin(1/{\sqrt {N}})\approx \pi {\sqrt {N}}/4}" loading="lazy">. Then the system is in state

</mrow>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<mrow>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mrow>

</mrow>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

<msup>

</mrow>

</msup>

<mrow>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mrow>

<mfrac>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

<mfrac>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle [|\omega \rangle \,|s\rangle ](U_{s}U_{\omega })^{r}{\begin{bmatrix}0\\1\end{bmatrix}}\approx [|\omega \rangle \,|s\rangle ]M{\begin{bmatrix}i&0\\0&-i\end{bmatrix}}M^{-1}{\begin{bmatrix}0\\1\end{bmatrix}}=|\omega \rangle {\frac {1}{\cos(t)}}-|s\rangle {\frac {\sin(t)}{\cos(t)}}.}</annotation>

</semantics>

</math>

A short calculation now shows that the observation yields the correct answer ω with error <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O\left({\frac {1}{N}}\right)}">

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O\left({\frac {1}{N}}\right)}</annotation>

</semantics>

</math><img src="./6de2d202fc315d78d7e12546e18df0672d8c9a52.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:8.481ex; height:6.176ex;" alt="{\displaystyle O\left({\frac {1}{N}}\right)}" loading="lazy">.

<div class="mw-heading mw-heading2"><h2 id="Extensions_and_variants">Extensions and variants</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Multiple_matching_entries">Multiple matching entries</h3></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">Further information: <a href="Amplitude_amplification" title="Amplitude amplification">Amplitude amplification</a></div>

If, instead of 1 matching entry, there are k matching entries, the same algorithm works, but the number of iterations must be <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle {\frac {\pi }{4}}{\left({\frac {N}{k}}\right)^{1/2}}}">

<mfrac>

</mfrac>

</mrow>

<msup>

<mrow>

<mfrac>

</mfrac>

</mrow>

</mrow>

</mrow>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle {\frac {\pi }{4}}{\left({\frac {N}{k}}\right)^{1/2}}}</annotation>

</semantics>

</math><img src="./90690f1aa38e0a04d844a25d682dc93d74781fca.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.838ex; width:9.547ex; height:5.343ex;" alt="{\textstyle {\frac {\pi }{4}}{\left({\frac {N}{k}}\right)^{1/2}}}" loading="lazy">instead of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle {\frac {\pi }{4}}{N^{1/2}}.}">

<mfrac>

</mfrac>

</mrow>

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle {\frac {\pi }{4}}{N^{1/2}}.}</annotation>

</semantics>

</math><img src="./124e9b052e044942cc42b05bdfe689bdd5901e95.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:7.246ex; height:3.509ex;" alt="{\textstyle {\frac {\pi }{4}}{N^{1/2}}.}" loading="lazy">

There are several ways to handle the case if k is unknown.<a href="#cite_note-16">[16]</a> A simple solution performs optimally up to a constant factor: run Grover's algorithm repeatedly for increasingly small values of k, e.g., taking k = N, N/2, N/4, ..., and so on, taking <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k=N/2^{t}}">

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k=N/2^{t}}</annotation>

</semantics>

</math><img src="./eaefcee0b071119684146019bf58015386b9f8bc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.524ex; height:3.009ex;" alt="{\displaystyle k=N/2^{t}}" loading="lazy"> for iteration t until a matching entry is found.

With sufficiently high probability, a marked entry will be found by iteration <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t=\log _{2}(N/k)+c}">

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t=\log _{2}(N/k)+c}</annotation>

</semantics>

</math><img src="./42f29e50c713c0ecba807349b3854b5d806c5ce9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.058ex; height:2.843ex;" alt="{\displaystyle t=\log _{2}(N/k)+c}" loading="lazy"> for some constant c. Thus, the total number of iterations taken is at most

<mfrac>

</mfrac>

</mrow>

</mrow>

<msqrt>

</msqrt>

</mrow>

<msqrt>

</msqrt>

</mrow>

<msqrt>

<mfrac>

<mrow>

<msup>

</mrow>

</msup>

</mrow>

</mfrac>

</msqrt>

</mrow>

</mrow>

</mrow>

<msqrt>

</mrow>

</msqrt>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {\pi }{4}}{\Big (}1+{\sqrt {2}}+{\sqrt {4}}+\cdots +{\sqrt {\frac {N}{k2^{c}}}}{\Big )}=O{\big (}{\sqrt {N/k}}{\big )}.}</annotation>

</semantics>

</math>

Another approach if k is unknown is to derive it via the <a href="Quantum_counting_algorithm" title="Quantum counting algorithm">quantum counting algorithm</a> prior.

If <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k=N/2}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k=N/2}</annotation>

</semantics>

</math><img src="./23c17e654c8d50e5477922a2233cf4aa844e0adc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.698ex; height:2.843ex;" alt="{\displaystyle k=N/2}" loading="lazy"> (or the traditional one marked state Grover's Algorithm if run with <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N=2}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N=2}</annotation>

</semantics>

</math><img src="./405d64b14536deffc3465f1e81b1b7fe9358ad2a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.325ex; height:2.176ex;" alt="{\displaystyle N=2}" loading="lazy">), the algorithm will provide no amplification. If <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k>N/2}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k>N/2}</annotation>

</semantics>

</math><img src="./5bd05f2300116fbad6f383b361aefbadaad9ebfa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.698ex; height:2.843ex;" alt="{\displaystyle k>N/2}" loading="lazy">, increasing k will begin to increase the number of iterations necessary to obtain a solution.<a href="#cite_note-17">[17]</a> On the other hand, if <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k\geq N/2}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k\geq N/2}</annotation>

</semantics>

</math><img src="./c37f54d816c95971f38fba3bca7f961c7546a67d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.698ex; height:2.843ex;" alt="{\displaystyle k\geq N/2}" loading="lazy">, a classical running of the checking oracle on a single random choice of input will more likely than not give a correct solution.

A version of this algorithm is used in order to solve the <a href="Collision_problem" title="Collision problem">collision problem</a>.<a href="#cite_note-Boyer-18">[18]</a><a href="#cite_note-19">[19]</a>

<div class="mw-heading mw-heading3"><h3 id="Quantum_partial_search">Quantum partial search</h3></div>

A modification of Grover's algorithm called quantum partial search was described by Grover and Radhakrishnan in 2004.<a href="#cite_note-20">[20]</a> In partial search, one is not interested in finding the exact address of the target item, only the first few digits of the address. Equivalently, we can think of "chunking" the search space into blocks, and then asking "in which block is the target item?". In many applications, such a search yields enough information if the target address contains the information wanted. For instance, to use the example given by L. K. Grover, if one has a list of students organized by class rank, we may only be interested in whether a student is in the lower 25%, 25–50%, 50–75% or 75–100% percentile.

To describe partial search, we consider a database separated into <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K}</annotation>

</semantics>

</math><img src="./2b76fce82a62ed5461908f0dc8f037de4e3686b0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.066ex; height:2.176ex;" alt="{\displaystyle K}" loading="lazy"> blocks, each of size <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b=N/K}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b=N/K}</annotation>

</semantics>

</math><img src="./71326f4f1b76342997c67ab5e3de7cc83952af4c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.388ex; height:2.843ex;" alt="{\displaystyle b=N/K}" loading="lazy">. The partial search problem is easier. Consider the approach we would take classically – we pick one block at random, and then perform a normal search through the rest of the blocks (in set theory language, the complement). If we do not find the target, then we know it is in the block we did not search. The average number of iterations drops from <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N/2}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N/2}</annotation>

</semantics>

</math><img src="./45c51c21b2bc7ea5e2fcae8f0f4aa49f6f19ebaf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.389ex; height:2.843ex;" alt="{\displaystyle N/2}" loading="lazy"> to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (N-b)/2}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (N-b)/2}</annotation>

</semantics>

</math><img src="./8e0edc1a22807d46715a182349f7d2e6fe0d0bcf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.036ex; height:2.843ex;" alt="{\displaystyle (N-b)/2}" loading="lazy">.

Grover's algorithm requires <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle {\frac {\pi }{4}}{\sqrt {N}}}">

<mfrac>

</mfrac>

</mrow>

<msqrt>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle {\frac {\pi }{4}}{\sqrt {N}}}</annotation>

</semantics>

</math><img src="./0e85666f2b8beb8344dada992e93db944fcf130b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:5.778ex; height:3.509ex;" alt="{\textstyle {\frac {\pi }{4}}{\sqrt {N}}}" loading="lazy"> iterations. Partial search will be faster by a numerical factor that depends on the number of blocks <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K}</annotation>

</semantics>

</math><img src="./2b76fce82a62ed5461908f0dc8f037de4e3686b0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.066ex; height:2.176ex;" alt="{\displaystyle K}" loading="lazy">. Partial search uses <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n_{1}}</annotation>

</semantics>

</math><img src="./ee784b70e772f55ede5e6e0bdc929994bff63413.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.449ex; height:2.009ex;" alt="{\displaystyle n_{1}}" loading="lazy"> global iterations and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n_{2}}</annotation>

</semantics>

</math><img src="./840e456e3058bc0be28e5cf653b170cdbfcc3be4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.449ex; height:2.009ex;" alt="{\displaystyle n_{2}}" loading="lazy"> local iterations. The global Grover operator is designated <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{1}}</annotation>

</semantics>

</math><img src="./e6ea4f4668b8334c8a7d3d284b0fd22131ef5f52.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.881ex; height:2.509ex;" alt="{\displaystyle G_{1}}" loading="lazy"> and the local Grover operator is designated <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G_{2}}</annotation>

</semantics>

</math><img src="./645011b0c6933a02f5f7d84624f78220d747427e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.881ex; height:2.509ex;" alt="{\displaystyle G_{2}}" loading="lazy">.

The global Grover operator acts on the blocks. Essentially, it is given as follows:

<ol><li>Perform <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j_{1}}</annotation>

</semantics>

</math><img src="./0a671019a672cd149a8d1584861e2f8fe9728a9e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:2.039ex; height:2.509ex;" alt="{\displaystyle j_{1}}" loading="lazy"> standard Grover iterations on the entire database.</li>

<li>Perform <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j_{2}}</annotation>

</semantics>

</math><img src="./9f29268662641c1e61d6faba764a493c74ba962b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:2.039ex; height:2.509ex;" alt="{\displaystyle j_{2}}" loading="lazy"> local Grover iterations. A local Grover iteration is a direct sum of Grover iterations over each block.</li>

<li>Perform one standard Grover iteration.</li></ol>

The optimal values of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j_{1}}</annotation>

</semantics>

</math><img src="./0a671019a672cd149a8d1584861e2f8fe9728a9e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:2.039ex; height:2.509ex;" alt="{\displaystyle j_{1}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j_{2}}</annotation>

</semantics>

</math><img src="./9f29268662641c1e61d6faba764a493c74ba962b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:2.039ex; height:2.509ex;" alt="{\displaystyle j_{2}}" loading="lazy"> are discussed in the paper by Grover and Radhakrishnan. One might also wonder what happens if one applies successive partial searches at different levels of "resolution". This idea was studied in detail by <a href="Vladimir_Korepin" title="Vladimir Korepin">Vladimir Korepin</a> and Xu, who called it binary quantum search. They proved that it is not in fact any faster than performing a single partial search.

<div class="mw-heading mw-heading2"><h2 id="Optimality">Optimality</h2></div>

Grover's algorithm is optimal up to sub-constant factors. That is, any algorithm that accesses the database only by using the operator Uω must apply Uω at least a <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1-o(1)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1-o(1)}</annotation>

</semantics>

</math><img src="./58661cb7ecc1c0b8a99a821365f8c179fdaabbec.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.102ex; height:2.843ex;" alt="{\displaystyle 1-o(1)}" loading="lazy"> fraction as many times as Grover's algorithm.<a href="#cite_note-21">[21]</a> The extension of Grover's algorithm to k matching entries, π(N/k)1/2/4, is also optimal.<a href="#cite_note-Boyer-18">[18]</a> This result is important in understanding the limits of quantum computation.

If the Grover's search problem was solvable with logc N applications of Uω, that would imply that <a href="NP_(complexity_class)" class="mw-redirect" title="NP (complexity class)">NP</a> is contained in <a href="BQP" title="BQP">BQP</a>, by transforming problems in NP into Grover-type search problems. The optimality of Grover's algorithm suggests that quantum computers cannot solve <a href="NP-completeness" title="NP-completeness">NP-Complete</a> problems in polynomial time, and thus NP is not contained in BQP.

It has been shown that a class of non-local <a href="Hidden-variable_theory" title="Hidden-variable theory">hidden variable</a> quantum computers could implement a search of an <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N}</annotation>

</semantics>

</math><img src="./f5e3890c981ae85503089652feb48b191b57aae3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.064ex; height:2.176ex;" alt="{\displaystyle N}" loading="lazy">-item database in at most <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O({\sqrt[{3}]{N}})}">

<mroot>

</mrow>

</mroot>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O({\sqrt[{3}]{N}})}</annotation>

</semantics>

</math><img src="./a953364313112d7f3243feb0c59146295a65263d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.582ex; height:3.176ex;" alt="{\displaystyle O({\sqrt[{3}]{N}})}" loading="lazy"> steps. This is faster than the <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O({\sqrt {N}})}">

<msqrt>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O({\sqrt {N}})}</annotation>

</semantics>

</math><img src="./6a8566840a0a5d4480a0b8ed63d0717c3a89ec9a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.582ex; height:3.176ex;" alt="{\displaystyle O({\sqrt {N}})}" loading="lazy"> steps taken by Grover's algorithm.<a href="#cite_note-22">[22]</a>

<ul><li><a href="Amplitude_amplification" title="Amplitude amplification">Amplitude amplification</a></li>

<li><a href="BHT_algorithm" title="BHT algorithm">Brassard–Høyer–Tapp algorithm</a> (for solving the <a href="Collision_problem" title="Collision problem">collision problem</a>)</li>

<li><a href="Shor's_algorithm" title="Shor's algorithm">Shor's algorithm</a> (for factorization)</li>

<li><a href="Quantum_walk_search" title="Quantum walk search">Quantum walk search</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Notes">Notes</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFGrover1996" class="citation book cs1">Grover, Lov K. (1996-07-01). <a rel="nofollow" class="external text" href="https://doi.org/10.1145/237814.237866">"A fast quantum mechanical algorithm for database search"</a>. Proceedings of the twenty-eighth annual ACM symposium on Theory of computing - STOC '96. Philadelphia, Pennsylvania, USA: Association for Computing Machinery. pp. 212–219. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/quant-ph/9605043">quant-ph/9605043</a>. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/1996quant.ph..5043G">1996quant.ph..5043G</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F237814.237866">10.1145/237814.237866</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-89791-785-8</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:207198067">207198067</a>.</cite>

</li>

<li id="cite_note-bennett_1997-2"><a href="#cite_ref-bennett_1997_2-0">^</a> <cite id="CITEREFBennettBernsteinBrassardVazirani1997" class="citation journal cs1">Bennett, C. H.; Bernstein, E.; Brassard, G.; Vazirani, U. (1997). <a rel="nofollow" class="external text" href="http://www.cs.berkeley.edu/~vazirani/pubs/bbbv.ps">"The strengths and weaknesses of quantum computation"</a>. <a href="SIAM_Journal_on_Computing" title="SIAM Journal on Computing">SIAM Journal on Computing</a>. 26 (5): 1510–1523. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/quant-ph/9701001">quant-ph/9701001</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2Fs0097539796300933">10.1137/s0097539796300933</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:13403194">13403194</a>.</cite>

</li>

<li id="cite_note-Nielsen-Chuang-3">^ <a href="#cite_ref-Nielsen-Chuang_3-0">a</a> <a href="#cite_ref-Nielsen-Chuang_3-1">b</a> <a href="#cite_ref-Nielsen-Chuang_3-2">c</a> <a href="#cite_ref-Nielsen-Chuang_3-3">d</a> <cite id="CITEREFNielsenChuang2010" class="citation book cs1">Nielsen, Michael A.; Chuang, Isaac L. (2010). Quantum computation and quantum information. Cambridge: Cambridge University Press. pp. 276–305. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-1-107-00217-3</bdi>. <a href="OCLC_(identifier)" class="mw-redirect" title="OCLC (identifier)">OCLC</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/oclc/665137861">665137861</a>.</cite>

</li>

<li id="cite_note-djb-groverr-4"><a href="#cite_ref-djb-groverr_4-0">^</a> <cite id="CITEREFBernstein2010" class="citation conference cs1"><a href="Daniel_J._Bernstein" title="Daniel J. Bernstein">Bernstein, Daniel J.</a> (2010). <a rel="nofollow" class="external text" href="https://cr.yp.to/codes/grovercode-20100303.pdf">"Grover vs. McEliece"</a> (PDF). In Sendrier, Nicolas (ed.). Post-Quantum Cryptography, Third International Workshop, PQCrypto 2010, Darmstadt, Germany, May 25-28, 2010. Proceedings. Lecture Notes in Computer Science. Vol. 6061. Springer. pp. 73–80. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-642-12929-2_6">10.1007/978-3-642-12929-2_6</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-642-12928-5</bdi>.</cite>

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> <cite id="CITEREFGrover1998" class="citation conference cs1">Grover, Lov K. (1998). "A framework for fast quantum mechanical algorithms". In Vitter, Jeffrey Scott (ed.). Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, Dallas, Texas, USA, May 23–26, 1998. Association for Computing Machinery. pp. 53–62. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/quant-ph/9711043">quant-ph/9711043</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F276698.276712">10.1145/276698.276712</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-89791-962-9</bdi>.</cite>

</li>

<li id="cite_note-Ambaianis04-6">^ <a href="#cite_ref-Ambaianis04_6-0">a</a> <a href="#cite_ref-Ambaianis04_6-1">b</a> <cite id="CITEREFAmbainis2004" class="citation journal cs1">Ambainis, A. (2004-06-01). <a rel="nofollow" class="external text" href="https://doi.org/10.1145/992287.992296">"Quantum search algorithms"</a>. ACM SIGACT News. 35 (2): 22–35. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/quant-ph/0504012">quant-ph/0504012</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F992287.992296">10.1145/992287.992296</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0163-5700">0163-5700</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:11326499">11326499</a>.</cite>

</li>

<li id="cite_note-7"><a href="#cite_ref-7">^</a> <cite id="CITEREFJordan" class="citation web cs1">Jordan, Stephen. <a rel="nofollow" class="external text" href="https://quantumalgorithmzoo.org">"Quantum Algorithm Zoo"</a>. quantumalgorithmzoo.org. Retrieved 2021-04-21.</cite>

</li>

<li id="cite_note-8"><a href="#cite_ref-8">^</a> <cite id="CITEREFCerfGroverWilliams2000" class="citation journal cs1">Cerf, Nicolas J.; Grover, Lov K.; Williams, Colin P. (2000-05-01). <a rel="nofollow" class="external text" href="https://doi.org/10.1007/s002000050134">"Nested Quantum Search and NP-Hard Problems"</a>. Applicable Algebra in Engineering, Communication and Computing. 10 (4): 311–338. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs002000050134">10.1007/s002000050134</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/1432-0622">1432-0622</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:311132">311132</a>.</cite>

</li>

<li id="cite_note-9"><a href="#cite_ref-9">^</a> <cite id="CITEREFAmbainis2007" class="citation journal cs1">Ambainis, Andris (2007-01-01). <a rel="nofollow" class="external text" href="https://epubs.siam.org/doi/10.1137/S0097539705447311">"Quantum Walk Algorithm for Element Distinctness"</a>. SIAM Journal on Computing. 37 (1): 210–239. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/quant-ph/0311001">quant-ph/0311001</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2FS0097539705447311">10.1137/S0097539705447311</a>. <a href="ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0097-5397">0097-5397</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:6581885">6581885</a>.</cite>

</li>

<li id="cite_note-10"><a href="#cite_ref-10">^</a> <cite id="CITEREFBrassardHøyerTapp1998" class="citation conference cs1">Brassard, Gilles; Høyer, Peter; Tapp, Alain (1998). "Quantum Cryptanalysis of Hash and Claw-Free Functions". In Lucchesi, Claudio L.; Moura, Arnaldo V. (eds.). LATIN '98: Theoretical Informatics, Third Latin American Symposium, Campinas, Brazil, April, 20-24, 1998, Proceedings. Lecture Notes in Computer Science. Vol. 1380. Springer. pp. 163–169. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/quant-ph/9705002">quant-ph/9705002</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBFb0054319">10.1007/BFb0054319</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-64275-6</bdi>.</cite>

</li>

<li id="cite_note-11"><a href="#cite_ref-11">^</a> <cite class="citation book cs1">Post-quantum cryptography. Daniel J. Bernstein, Johannes Buchmann, Erik, Dipl.-Math Dahmén. Berlin: Springer. 2009. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-540-88702-7</bdi>. <a href="OCLC_(identifier)" class="mw-redirect" title="OCLC (identifier)">OCLC</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/oclc/318545517">318545517</a>.</cite><code class="cs1-code">{{cite book}}</code>: CS1 maint: others (link)

</li>

<li id="cite_note-12"><a href="#cite_ref-12">^</a> <cite id="CITEREFBernstein2021" class="citation journal cs1">Bernstein, Daniel J. (2021-04-21). <a rel="nofollow" class="external text" href="https://www.hyperelliptic.org/tanja/SHARCS/record2.pdf#page=113">"Cost analysis of hash collisions: Will quantum computers make SHARCS obsolete?"</a> (PDF). Conference Proceedings for Special-purpose Hardware for Attacking Cryptographic Systems (SHARCS '09). 09: 105–117.</cite>

</li>

<li id="cite_note-Viamontes-13"><a href="#cite_ref-Viamontes_13-0">^</a> <cite id="CITEREFViamontes_G.F.Markov_I.L.Hayes_J.P.2005" class="citation cs2">Viamontes G.F.; Markov I.L.; Hayes J.P. (2005), <a rel="nofollow" class="external text" href="https://web.eecs.umich.edu/~imarkov/pubs/jour/cise05-grov.pdf">"Is Quantum Search Practical?"</a> (PDF), Computing in Science and Engineering, 7 (3): 62–70, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/quant-ph/0405001">quant-ph/0405001</a>, <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2005CSE.....7c..62V">2005CSE.....7c..62V</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2Fmcse.2005.53">10.1109/mcse.2005.53</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:8929938">8929938</a></cite>

</li>

<li id="cite_note-sinitsyn23-14"><a href="#cite_ref-sinitsyn23_14-0">^</a> <cite id="CITEREFSinitsyn_N._A.Yan_B.2023" class="citation journal cs1">Sinitsyn N. A.; Yan B. (2023). "Topologically protected Grover's oracle for the partition problem". Physical Review A. 108 (2): 022412. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/2304.10488">2304.10488</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1103%2FPhysRevA.108.022412">10.1103/PhysRevA.108.022412</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:258236417">258236417</a>.</cite>

</li>

<li id="cite_note-15"><a href="#cite_ref-15">^</a> <cite id="CITEREFBabbushMcCleanNewmanGidney2021" class="citation journal cs1">Babbush, Ryan; McClean, Jarrod R.; Newman, Michael; Gidney, Craig; Boixo, Sergio; Neven, Hartmut (2021-03-29). <a rel="nofollow" class="external text" href="https://doi.org/10.1103%2FPRXQuantum.2.010103">"Focus beyond Quadratic Speedups for Error-Corrected Quantum Advantage"</a>. PRX Quantum. 2 (1): 010103. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/2011.04149">2011.04149</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1103%2FPRXQuantum.2.010103">10.1103/PRXQuantum.2.010103</a>.</cite>

</li>

<li id="cite_note-16"><a href="#cite_ref-16">^</a> <cite id="CITEREFAaronson2021" class="citation web cs1">Aaronson, Scott (April 19, 2021). <a rel="nofollow" class="external text" href="https://www.scottaaronson.com/qclec.pdf">"Introduction to Quantum Information Science Lecture Notes"</a> (PDF).</cite>

</li>

<li id="cite_note-17"><a href="#cite_ref-17">^</a> Nielsen-Chuang

</li>

<li id="cite_note-Boyer-18">^ <a href="#cite_ref-Boyer_18-0">a</a> <a href="#cite_ref-Boyer_18-1">b</a> <cite id="CITEREFBoyerBrassardHøyerTapp1998" class="citation cs2">Boyer, Michel; Brassard, Gilles; Høyer, Peter; Tapp, Alain (1998), "Tight Bounds on Quantum Searching", Fortschritte der Physik, 46 (4–5): 493–506, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/quant-ph/9605034">quant-ph/9605034</a>, <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/1998ForPh..46..493B">1998ForPh..46..493B</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1002%2F3527603093.ch10">10.1002/3527603093.ch10</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9783527603091</bdi></cite>

</li>

<li id="cite_note-19"><a href="#cite_ref-19">^</a> <cite id="CITEREFAmbainis2004" class="citation cs2">Ambainis, Andris (2004), "Quantum search algorithms", SIGACT News, 35 (2): 22–35, <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/quant-ph/0504012">quant-ph/0504012</a>, <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2005quant.ph..4012A">2005quant.ph..4012A</a>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F992287.992296">10.1145/992287.992296</a>, <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:11326499">11326499</a></cite>

</li>

<li id="cite_note-20"><a href="#cite_ref-20">^</a> <cite id="CITEREFGroverRadhakrishnan2005" class="citation arxiv cs1">Grover, L. K.; Radhakrishnan, J. (2005-02-07). "Is partial quantum search of a database any easier?". <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/quant-ph/0407122v4">quant-ph/0407122v4</a>.</cite>

</li>

<li id="cite_note-21"><a href="#cite_ref-21">^</a> <cite id="CITEREFZalka1999" class="citation journal cs1">Zalka, Christof (1999-10-01). <a rel="nofollow" class="external text" href="https://link.aps.org/doi/10.1103/PhysRevA.60.2746">"Grover's quantum searching algorithm is optimal"</a>. Physical Review A. 60 (4): 2746–2751. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<a rel="nofollow" class="external text" href="https://arxiv.org/abs/quant-ph/9711070">quant-ph/9711070</a>. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/1999PhRvA..60.2746Z">1999PhRvA..60.2746Z</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1103%2FPhysRevA.60.2746">10.1103/PhysRevA.60.2746</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:1542077">1542077</a>.</cite>

</li>

<li id="cite_note-22"><a href="#cite_ref-22">^</a> <cite id="CITEREFAaronson" class="citation web cs1">Aaronson, Scott. <a rel="nofollow" class="external text" href="http://www.scottaaronson.com/papers/qchvpra.pdf">"Quantum Computing and Hidden Variables"</a> (PDF).</cite>

</li>

</ol></div>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

<ul><li>Grover L.K.: <a rel="nofollow" class="external text" href="https://arxiv.org/abs/quant-ph/9605043">A fast quantum mechanical algorithm for database search</a>, Proceedings, 28th Annual ACM Symposium on the Theory of Computing, (May 1996) p. 212</li>

<li>Grover L.K.: <a rel="nofollow" class="external text" href="https://arxiv.org/abs/quant-ph/0109116">From Schrödinger's equation to quantum search algorithm</a>, American Journal of Physics, 69(7): 769–777, 2001. Pedagogical review of the algorithm and its history.</li>

<li>Grover L.K.: <a rel="nofollow" class="external text" href="https://cryptome.org/qc-grover.htm">QUANTUM COMPUTING: How the weird logic of the subatomic world could make it possible for machines to calculate millions of times faster than they do today</a> The Sciences, July/August 1999, pp. 24–30.</li>

<li>Nielsen, M.A. and Chuang, I.L. Quantum computation and quantum information. Cambridge University Press, 2000. Chapter 6.</li>

<li><a rel="nofollow" class="external text" href="https://web.archive.org/web/20140201230754/http://www.bell-labs.com/user/feature/archives/lkgrover/">What's a Quantum Phone Book?</a>, Lov Grover, Lucent Technologies</li></ul>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .side-box{margin:4px 0;box-sizing:border-box;border:1px solid #aaa;font-size:88%;line-height:1.25em;background-color:var(--background-color-interactive-subtle,#f8f9fa);display:flow-root}.mw-parser-output .infobox .side-box{font-size:100%}.mw-parser-output .side-box-abovebelow,.mw-parser-output .side-box-text{padding:0.25em 0.9em}.mw-parser-output .side-box-image{padding:2px 0 2px 0.9em;text-align:center}.mw-parser-output .side-box-imageright{padding:2px 0.9em 2px 0;text-align:center}@media(min-width:500px){.mw-parser-output .side-box-flex{display:flex;align-items:center}.mw-parser-output .side-box-text{flex:1;min-width:0}}@media(min-width:720px){.mw-parser-output .side-box{width:238px}.mw-parser-output .side-box-right{clear:right;float:right;margin-left:1em}.mw-parser-output .side-box-left{margin-right:1em}}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1237033735">

/* start https://en.wikipedia.org/ */

@media print{body.ns-0 .mw-parser-output .sistersitebox{display:none!important}}@media screen{html.skin-theme-clientpref-night .mw-parser-output .sistersitebox img[src*="Wiktionary-logo-en-v2.svg"]{background-color:white}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .sistersitebox img[src*="Wiktionary-logo-en-v2.svg"]{background-color:white}}

/* end https://en.wikipedia.org/ */

</style><div class="side-box side-box-right sistersitebox"><style data-mw-deduplicate="TemplateStyles:r1126788409">

/* start https://en.wikipedia.org/ */

.mw-parser-output .plainlist ol,.mw-parser-output .plainlist ul{line-height:inherit;list-style:none;margin:0;padding:0}.mw-parser-output .plainlist ol li,.mw-parser-output .plainlist ul li{margin-bottom:0}

/* end https://en.wikipedia.org/ */

</style>

<div class="side-box-text plainlist">Wikiquote has quotations related to <a href="https://en.wikiquote.org/wiki/Special:Search/Grover%27s_algorithm" class="extiw external" title="q:Special:Search/Grover's algorithm">Grover's algorithm</a>.</div></div>

</div>

<ul><li><cite id="CITEREFDavy_Wybiral" class="citation web cs1">Davy Wybiral. <a rel="nofollow" class="external text" href="https://web.archive.org/web/20170116155032/http://davy.wtf/quantum/?example=Grover%27s%20Algorithm">"Quantum Circuit Simulator"</a>. Archived from <a rel="nofollow" class="external text" href="http://davy.wtf/quantum/?example=Grover%27s%20Algorithm">the original</a> on 2017-01-16. Retrieved 2017-01-13.</cite></li>

<li><cite id="CITEREFCraig_Gidney2013" class="citation web cs1">Craig Gidney (2013-03-05). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20201117095032/http://twistedoakstudios.com/blog/Post2644_grovers-quantum-search-algorithm">"Grover's Quantum Search Algorithm"</a>. Archived from <a rel="nofollow" class="external text" href="http://twistedoakstudios.com/blog/Post2644_grovers-quantum-search-algorithm">the original</a> on 2020-11-17. Retrieved 2013-03-08.</cite></li>

<li><cite id="CITEREFFrançois_Schwarzentruber2013" class="citation web cs1">François Schwarzentruber (2013-05-18). <a rel="nofollow" class="external text" href="http://people.irisa.fr/Francois.Schwarzentruber/mit1_algo2_2013/grover_s_algorithm/">"Grover's algorithm"</a>.</cite></li>

<li><cite id="CITEREFAlexander_Prokopenya" class="citation web cs1">Alexander Prokopenya. <a rel="nofollow" class="external text" href="http://demonstrations.wolfram.com/QuantumCircuitImplementingGroversSearchAlgorithm/">"Quantum Circuit Implementing Grover's Search Algorithm"</a>. <a href="Wolfram_Alpha" class="mw-redirect" title="Wolfram Alpha">Wolfram Alpha</a>.</cite></li>

<li><cite class="citation cs2"><a rel="nofollow" class="external text" href="https://www.encyclopediaofmath.org/index.php?title=Quantum_computation,_theory_of">"Quantum computation, theory of"</a>, <a href="Encyclopedia_of_Mathematics" title="Encyclopedia of Mathematics">Encyclopedia of Mathematics</a>, <a href="European_Mathematical_Society" title="European Mathematical Society">EMS Press</a>, 2001 [1994]</cite></li>

<li><cite id="CITEREFRoberto_Maestre2018" class="citation web cs1">Roberto Maestre (2018-05-11). <a rel="nofollow" class="external text" href="https://github.com/rmaestre/quantumSystem">"Grover's Algorithm implemented in R and C"</a>. <a href="GitHub" title="GitHub">GitHub</a>.</cite></li>

<li><cite id="CITEREFBernhard_Ömer" class="citation web cs1">Bernhard Ömer. <a rel="nofollow" class="external text" href="http://tph.tuwien.ac.at/~oemer/qcl.html">"QCL - A Programming Language for Quantum Computers"</a>. Retrieved 2022-04-30. <q>Implemented in /qcl-0.6.4/lib/grover.qcl</q></cite></li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Quantum_information_science667" style="padding:3px"><table class="nowraplinks hlist mw-collapsible mw-collapsed navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Quantum_information_science667" style="font-size:114%;margin:0 4em"><a href="Quantum_information_science" title="Quantum information science">Quantum information science</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">General</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="DiVincenzo's_criteria" title="DiVincenzo's criteria">DiVincenzo's criteria</a></li>

<li><a href="Quantum_computing" title="Quantum computing">Quantum computing</a>

<ul><li><a href="Timeline_of_quantum_computing_and_communication" title="Timeline of quantum computing and communication">timeline</a></li></ul></li>

<li><a href="Quantum_information" title="Quantum information">Quantum information</a></li>

<li><a href="Quantum_programming" title="Quantum programming">Quantum programming</a></li>

<li><a href="Quantum_simulator" title="Quantum simulator">Quantum simulation</a></li>

<li><a href="Qubit" title="Qubit">Qubit</a>

<ul><li><a href="Physical_and_logical_qubits" title="Physical and logical qubits">physical vs. logical</a></li></ul></li>

<li><a href="List_of_quantum_processors" title="List of quantum processors">Quantum processors</a>

<ul><li><a href="Cloud-based_quantum_computing" title="Cloud-based quantum computing">cloud-based</a></li></ul></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Theorems</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<li><a href="Eastin%E2%80%93Knill_theorem" title="Eastin–Knill theorem">Eastin–Knill</a></li>

<li><a href="Gleason's_theorem" title="Gleason's theorem">Gleason's</a></li>

<li><a href="Gottesman%E2%80%93Knill_theorem" title="Gottesman–Knill theorem">Gottesman–Knill</a></li>

<li><a href="Holevo's_theorem" title="Holevo's theorem">Holevo's</a></li>

<li><a href="No-broadcasting_theorem" title="No-broadcasting theorem">No-broadcasting</a></li>

<li><a href="No-cloning_theorem" title="No-cloning theorem">No-cloning</a></li>

<li><a href="No-communication_theorem" title="No-communication theorem">No-communication</a></li>

<li><a href="No-deleting_theorem" title="No-deleting theorem">No-deleting</a></li>

<li><a href="No-hiding_theorem" title="No-hiding theorem">No-hiding</a></li>

<li><a href="No-teleportation_theorem" title="No-teleportation theorem">No-teleportation</a></li>

<li><a href="Quantum_speed_limit_theorems" class="mw-redirect" title="Quantum speed limit theorems">Quantum speed limit</a></li>

<li><a href="Threshold_theorem" title="Threshold theorem">Threshold</a></li>

<li><a href="Solovay%E2%80%93Kitaev_theorem" title="Solovay–Kitaev theorem">Solovay–Kitaev</a></li>

<li><a href="Schr%C3%B6dinger%E2%80%93HJW_theorem" class="mw-redirect" title="Schrödinger–HJW theorem">Schrödinger-HJW</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Quantum communication</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Classical_capacity" title="Classical capacity">Classical capacity</a>

<ul><li><a href="Entanglement-assisted_classical_capacity" title="Entanglement-assisted classical capacity">entanglement-assisted</a></li>

<li><a href="Quantum_capacity" title="Quantum capacity">quantum capacity</a></li></ul></li>

<li><a href="Entanglement_distillation" title="Entanglement distillation">Entanglement distillation</a></li>

<li><a href="Entanglement_swapping" title="Entanglement swapping">Entanglement swapping</a></li>

<li><a href="Monogamy_of_entanglement" title="Monogamy of entanglement">Monogamy of entanglement</a></li>

<li><a href="Quantum_channel" title="Quantum channel">Quantum channel</a>

<ul><li><a href="Quantum_network" title="Quantum network">quantum network</a></li></ul></li>

<li><a href="Quantum_state_purification" title="Quantum state purification">State purification</a></li>

<li><a href="Quantum_teleportation" title="Quantum teleportation">Quantum teleportation</a>

<ul><li><a href="Quantum_energy_teleportation" title="Quantum energy teleportation">quantum energy teleportation</a></li>

<li><a href="Quantum_gate_teleportation" title="Quantum gate teleportation">quantum gate teleportation</a></li></ul></li>

<li><a href="Superdense_coding" title="Superdense coding">Superdense coding</a></li></ul>

</div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th id="Quantum_cryptography24" scope="row" class="navbox-group" style="width:1%"><a href="Quantum_cryptography" title="Quantum cryptography">Quantum cryptography</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Post-quantum_cryptography" title="Post-quantum cryptography">Post-quantum cryptography</a></li>

<li><a href="Quantum_coin_flipping" title="Quantum coin flipping">Quantum coin flipping</a></li>

<li><a href="Quantum_money" title="Quantum money">Quantum money</a></li>

<li><a href="Quantum_key_distribution" title="Quantum key distribution">Quantum key distribution</a>

<li><a href="List_of_quantum_key_distribution_protocols" title="List of quantum key distribution protocols">other protocols</a></li></ul></li>

<li><a href="Quantum_secret_sharing" title="Quantum secret sharing">Quantum secret sharing</a></li></ul>

</div></td></tr></tbody></table><div>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Quantum_algorithm" title="Quantum algorithm">Quantum algorithms</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Algorithmic_cooling" title="Algorithmic cooling">Algorithmic cooling</a></li>

<li><a href="Amplitude_amplification" title="Amplitude amplification">Amplitude amplification</a></li>

<li><a href="Bernstein%E2%80%93Vazirani_algorithm" title="Bernstein–Vazirani algorithm">Bernstein–Vazirani</a></li>

<li><a href="Boson_sampling" title="Boson sampling">Boson sampling</a></li>

<li><a href="Deutsch%E2%80%93Jozsa_algorithm" title="Deutsch–Jozsa algorithm">Deutsch–Jozsa</a></li>

<li><a href="Hidden_subgroup_problem" title="Hidden subgroup problem">Hidden subgroup</a></li>

<li><a href="Magic_state_distillation" title="Magic state distillation">Magic state distillation</a></li>

<li><a href="Quantum_annealing" title="Quantum annealing">Quantum annealing</a></li>

<li><a href="Quantum_counting_algorithm" title="Quantum counting algorithm">Quantum counting</a></li>

<li><a href="Quantum_Fourier_transform" title="Quantum Fourier transform">Quantum Fourier transform</a></li>

<li><a href="Quantum_optimization_algorithms" title="Quantum optimization algorithms">Quantum optimization</a></li>

<li><a href="Quantum_phase_estimation_algorithm" title="Quantum phase estimation algorithm">Quantum phase estimation</a></li>

<li><a href="Simon's_problem" title="Simon's problem">Simon's</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Quantum_complexity_theory" title="Quantum complexity theory">Quantum complexity theory</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<li><a href="PostBQP" title="PostBQP">PostBQP</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Quantum processor benchmarks</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Quantum_supremacy" title="Quantum supremacy">Quantum supremacy</a></li>

<li><a href="Quantum_volume" title="Quantum volume">Quantum volume</a></li>

<li><a href="Randomized_benchmarking" title="Randomized benchmarking">Randomized benchmarking</a>

<li><a href="Relaxation_(NMR)" title="Relaxation (NMR)">Relaxation times</a>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Quantum <a href="Model_of_computation" title="Model of computation">computing models</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Adiabatic_quantum_computation" title="Adiabatic quantum computation">Adiabatic quantum computation</a></li>

<li><a href="Continuous-variable_quantum_information" title="Continuous-variable quantum information">Continuous-variable quantum information</a></li>

<li><a href="One-way_quantum_computer" title="One-way quantum computer">One-way quantum computer</a>

<ul><li><a href="Cluster_state" title="Cluster state">cluster state</a></li></ul></li>

<li><a href="Quantum_circuit" title="Quantum circuit">Quantum circuit</a>

<ul><li><a href="Quantum_logic_gate" title="Quantum logic gate">quantum logic gate</a></li></ul></li>

<li><a href="Quantum_machine_learning" title="Quantum machine learning">Quantum machine learning</a>

<ul><li><a href="Quantum_neural_network" title="Quantum neural network">quantum neural network</a></li></ul></li>

<li><a href="Quantum_Turing_machine" title="Quantum Turing machine">Quantum Turing machine</a></li>

<li><a href="Topological_quantum_computer" title="Topological quantum computer">Topological quantum computer</a></li>

<li><a href="Hamiltonian_quantum_computation" title="Hamiltonian quantum computation">Hamiltonian quantum computation</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Quantum_error_correction" title="Quantum error correction">Quantum error correction</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li>Codes

<ul><li><a href="Five-qubit_error_correcting_code" title="Five-qubit error correcting code">5 qubit</a></li>

<li><a href="Quantum_convolutional_code" title="Quantum convolutional code">quantum convolutional</a></li>

<li><a href="Stabilizer_code" title="Stabilizer code">stabilizer</a></li>

<li><a href="Bacon%E2%80%93Shor_code" title="Bacon–Shor code">Bacon–Shor</a></li>

<li><a href="Steane_code" title="Steane code">Steane</a></li>

<li><a href="Toric_code" title="Toric code">Toric</a></li>

<li><a href="Entanglement-assisted_stabilizer_formalism" title="Entanglement-assisted stabilizer formalism">Entanglement-assisted</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Physical implementations</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Quantum_optics" title="Quantum optics">Quantum optics</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Cavity_quantum_electrodynamics" title="Cavity quantum electrodynamics">Cavity QED</a></li>

<li><a href="Circuit_quantum_electrodynamics" title="Circuit quantum electrodynamics">Circuit QED</a></li>

<li><a href="Linear_optical_quantum_computing" title="Linear optical quantum computing">Linear optical QC</a></li>

<li><a href="KLM_protocol" title="KLM protocol">KLM protocol</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Ultracold_atom" title="Ultracold atom">Ultracold atoms</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Neutral_atom_quantum_computer" title="Neutral atom quantum computer">Neutral atom QC</a></li>

<li><a href="Trapped-ion_quantum_computer" title="Trapped-ion quantum computer">Trapped-ion QC</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Spin_(physics)" title="Spin (physics)">Spin</a>-based</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<li><a href="Spin_qubit_quantum_computer" title="Spin qubit quantum computer">Spin qubit QC</a></li>

<li><a href="Nitrogen-vacancy_center" title="Nitrogen-vacancy center">NV center</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Superconducting_quantum_computing" title="Superconducting quantum computing">Superconducting</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Charge_qubit" title="Charge qubit">Charge qubit</a></li>

<li><a href="Flux_qubit" title="Flux qubit">Flux qubit</a></li>

<li><a href="Phase_qubit" title="Phase qubit">Phase qubit</a></li>

<li><a href="Transmon" title="Transmon">Transmon</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Quantum_programming" title="Quantum programming">Quantum programming</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="OpenQASM" title="OpenQASM">OpenQASM</a>–<a href="Qiskit" title="Qiskit">Qiskit</a>–<a href="IBM_Quantum_Experience" class="mw-redirect" title="IBM Quantum Experience">IBM QX</a></li>

<li><a href="Quil_(instruction_set_architecture)" title="Quil (instruction set architecture)">Quil</a>–<a href="Rigetti_Computing" title="Rigetti Computing">Forest/Rigetti QCS</a></li>

<li><a href="Libquantum" title="Libquantum">libquantum</a></li>

<li><a href="Quantum_programming" title="Quantum programming">many others...</a></li></ul>

</div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div>

<ul><li> Quantum information science</li>

<li> Quantum mechanics topics</li></ul>

</div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-07-17" href="https://en.wikipedia.org/wiki/?title=Grover's_algorithm&oldid=1300965615">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>